#include "link_list.h"

//1.1创建节点的函数
int create_node(node_t** pnew, int data)
{
    *pnew = (node_t*)malloc(sizeof(node_t));
    if(*pnew == NULL)
    {
        printf("%s-%s(%d):空间分配失败\n",__FILE__,__func__,__LINE__);
        exit(-1);
    }
    (*pnew)->next = NULL;
    (*pnew)->data = data;

    return 0;
}

//2.1头插法
int insert_from_link_by_head(node_t* phead, int data)
{
    if(phead == NULL)
    {
        printf("%s-%s(%d):空间分配失败\n",__FILE__,__func__,__LINE__);
        exit(-1);
    }
    node_t* ptemp = phead;
    node_t* pnew = NULL;
    create_node(&pnew, data);
    pnew->next = phead->next;
    phead->next = pnew;

    return 0;
}

//2.2尾插法
int insert_from_link_by_tail(node_t* phead, int data)
{
    if(phead == NULL)
    {
        printf("%s-%s(%d):空间分配失败\n",__FILE__,__func__,__LINE__);
        exit(-1);
    }
    node_t* ptemp = phead;
    node_t* pnew = NULL;
    create_node(&pnew, data);
    while(ptemp->next != NULL)  //※此条件第一次写错
    {
        ptemp = ptemp->next;
    }
    ptemp->next = pnew;
}

//2.3任意位置插入
int insert_from_link_by_pos(node_t* phead, int pos, int data)
{
    if(phead == NULL)
    {
        printf("%s-%s(%d):空间分配失败\n",__FILE__,__func__,__LINE__);
        exit(-1);
    }
    node_t* ptemp = phead;
    if(pos<1)//对pos前的不合理值进行判断
    {
        printf("%s-%s(%d):插入位置不合理 插入失败\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    int i = 0;
    for(i = 0; i < pos-1; i++)  //对插入位置的合理性进行检查
    {
        if(ptemp->next != NULL)
        {
            ptemp = ptemp->next;
        }
        else
        {
            printf("%s-%s(%d):插入位置不合理 插入失败\n",__FILE__,__func__,__LINE__);
            return -1;
        }
    }
    node_t *pnew = NULL;
    create_node(&pnew, data);

    pnew->next = ptemp->next;
    ptemp->next = pnew;
    return 0;
}

//3.1头删法
int delete_from_list_by_head(node_t *phead)
{
    if(NULL == phead)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    if(phead->next == NULL)
    {
        printf("%s-%s(%d):链表为空 删除失败\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    //※保存要删除的节点(必须采用pdel保存，如果不保存那么free的时候将会找不到地址)
    node_t *pdel = phead->next;
    phead->next = pdel->next;
    free(pdel);
    pdel = NULL;
    return 0;
}

//3.2尾删法
int delete_from_link_by_tail(node_t *phead)
{
    if(NULL == phead)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    if(phead->next == NULL)
    {
        printf("%s-%s(%d):链表为空 删除失败\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    //先找到倒数第二个节点 作为待删除节点的前一节点
    node_t *ptemp = phead;
    while(ptemp->next->next != NULL)
    {
        ptemp = ptemp->next;
    }
    //当循环结束的时候 ptemp 指向的就是倒数第二个节点
    free(ptemp->next);
    ptemp->next = NULL;
    return 0;
}

//3.3任意位置删除
int delete_from_link_by_pos(node_t* phead, int pos)
{
    if(NULL == phead)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    if(phead->next == NULL)
    {
        printf("%s-%s(%d):链表为空 删除失败\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    if(pos<1)
    {
        printf("%s-%s(%d):删除位置不合理 删除失败\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    node_t* ptemp = phead;
    int i = 0;
    for(i = 0; i < pos-1 && ptemp->next != NULL; i++)   
    {
        ptemp = ptemp->next;
    }
    if(ptemp->next == NULL) //和上一个判断条件结合
    {
        printf("%s-%s(%d):删除位置不合理 删除失败\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    node_t* pdel = NULL;
    pdel = ptemp->next;
    ptemp->next = pdel->next;
    free(pdel);
    pdel = NULL;

    return 0;
}

//4.1清空链表----清空所有的数据节点，只保留头节点
int clean_link(node_t *phead)
{
    if(NULL == phead)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    //循环头删
    node_t *ptemp = phead;
    node_t *pdel = NULL;
    while(ptemp->next != NULL)
    {
        pdel = ptemp->next;
        ptemp->next = pdel->next;
        //ptemp->next = ptemp->next->next;//这种写法也可以
        free(pdel);
    }
    pdel = NULL;
    return 0;
}

//5.1销毁链表
int destroy_link(node_t** phead)
{
    if(NULL == phead)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    if((*phead)->next != NULL)
    {
        clean_link(*phead);
    }
    free(*phead);
    *phead = NULL;

    return 0;
}

//6.1查找链表中是否有要寻找的数据
int find_data(node_t* phead, int value)
{
    if(phead == NULL)
    {
        printf("%s-%s(%d):空间分配失败\n",__FILE__,__func__,__LINE__);
        exit(-1);
    }
    node_t* ptemp = phead;
    while(ptemp->next != NULL)
    {
        if(ptemp->next->data == value)
        {
            return 1;
        }
        ptemp = ptemp->next;
    }

    return 0;
}

//7.1链表的排序
int sort_link(node_t* phead)
{
    if(NULL == phead)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    //只有头结点  无需排序
    if(NULL == phead->next)
    {
        printf("%s-%s(%d):只有头结点 无需排序\n",__FILE__,__func__,__LINE__);
        return 0;
    }
    //只有一个数据节点时  也无需排序
    if(NULL == phead->next->next)
    {
        printf("%s-%s(%d):只有一个节点 无需排序\n",__FILE__,__func__,__LINE__);
        return 0;
    }
    node_t* p = phead->next;
    node_t* q = p->next;
    int temp = 0;
    while(p->next != NULL)
    {
        while(q->next != NULL)
        {
            if(p->data > q->data)
            {
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            q = q->next;
        }
        p = p->next;
    }
    
    return 0;
}

//7.2链表的合并 将phead_2 合并到 phead_1的后面
int merge_link_list(node_t* phead_1, node_t** phead_2)
{
    if(NULL == phead_1 || NULL == phead_2 || NULL == *phead_2)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    //先找到phead_1的最后一个节点
    node_t* ptemp = phead_1;
    while(ptemp->next != NULL)
    {
        ptemp = ptemp->next;
    }
    ptemp->next = (*phead_2)->next;
    free(*phead_2);
    *phead_2 = NULL;
    
    return 0;
}

//7.3链表的翻转
int reverse_link_list(node_t *phead)
{
    if(NULL == phead)
    {
        printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);
        return -1;
    }
    //只有头结点  无需翻转
    if(NULL == phead->next)
    {
        printf("%s-%s(%d):只有头结点 无需翻转\n",__FILE__,__func__,__LINE__);
        return 0;
    }
    //只有一个数据节点时  也无需翻转
    if(NULL == phead->next->next)
    {
        printf("%s-%s(%d):只有一个节点 无需翻转\n",__FILE__,__func__,__LINE__);
        return 0;
    }
    //翻转的逻辑
    node_t *p = phead->next->next;
    node_t *q = NULL;
    phead->next->next = NULL;

    while(p != NULL)
    {
        //先保存p的指针域  否则就找不到了
        q = p->next;

        //将p 头插到原链表中
        p->next = phead->next;
        phead->next = p;

        //p往后走
        p = q;
    }
    return 0;
}

//8.1遍历链表的节点----学习阶段看现象用的
int show_data(node_t* phead)
{
    if(phead == NULL)
    {
        printf("%s-%s(%d):空间分配失败\n",__FILE__,__func__,__LINE__);
        exit(-1);
    }
    node_t* ptemp = phead;
    while(ptemp->next != NULL)
    {
        ptemp = ptemp->next;
        printf("%d ",ptemp->data);
    }
    putchar(10);
    return 0;
}